package com.example.arithmeticleetcode.leetcode.s2021.july;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.nio.charset.StandardCharsets;
import java.time.DayOfWeek;
import java.time.Instant;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;
import java.time.Period;
import java.time.ZoneOffset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Base64;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
import java.util.UUID;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.function.Function;
import java.util.stream.Collectors;

import org.apache.commons.lang3.ObjectUtils;
import org.springframework.beans.BeanUtils;
import org.springframework.util.DigestUtils;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.Getter;
import lombok.RequiredArgsConstructor;
import lombok.var;

/**
 * @author fangzhen@focusmedia.cn
 * @creation time 2021/7/26
 */
public class Demo01 {

    /**
     * 5823. 字符串转化后的各位数字之和
     *
     * @param s
     * @param k
     * @return
     */
    public int getLucky(String s, int k) {
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            sb.append(aChar - 96);
        }
        int startIndex = 0;
        int sum = 0;
        while (k-- > 0) {
            sum = 0;
            int len = sb.length();
            while (startIndex < len) {
                sum += sb.charAt(startIndex++) - 48;
            }
            sb.append(sum);
            if (sum < 10) {
                return sum;
            }
        }
        return sum;

    }

    /**
     * 1946. 子字符串突变后可能得到的最大整数
     *
     * @param num
     * @param change
     * @return
     */
    public String maximumNumber(String num, int[] change) {
        char[] chars = num.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - '0';
            if (change[index] > index) {
                while (i < chars.length && change[chars[i] - '0'] >= chars[i] - '0') {
                    chars[i] = (char) ('0' + change[chars[i] - '0']);
                    i++;
                }
                break;
            }
        }
        return new String(chars);
    }

    int ans;
    int rootValue;

    /**
     * 671. 二叉树中第二小的节点
     *
     * @param root
     * @return
     */
    public int findSecondMinimumValue(TreeNode root) {
        ans = -1;
        rootValue = root.val;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        if (ans != -1 && node.val >= ans) {
            return;
        }
        if (node.val > rootValue) {
            ans = node.val;
        }
        dfs(node.left);
        dfs(node.right);
    }

    /**
     * 145. 二叉树的后序遍历 递归方式实现
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        return list;
    }


    private void dfs(TreeNode node, List<Integer> list) {
        if (node == null) return;
        dfs(node.left, list);
        dfs(node.right, list);
        list.add(node.val);
    }

    /**
     * 145. 二叉树的后序遍历 非递归形式实现
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }

//    public static void main(String[] args) {
//        BigDecimal bigDecimal1 = new BigDecimal("15");
//        BigDecimal bigDecimal2 = new BigDecimal("15.0");
//        System.out.println(bigDecimal1.compareTo(bigDecimal2));
//        System.out.println(bigDecimal1.subtract(bigDecimal2).compareTo(BigDecimal.ZERO));
//        String DATE_FORMAT = "yyyy-MM-dd";
//        Instant now = Instant.now();
//        System.out.println(now);
//        LocalDateTime ldt = LocalDateTime.ofInstant(now, ZoneId.systemDefault());
//        String format = DateTimeFormatter.ofPattern(DATE_FORMAT).format(ldt);
//        System.out.println(format);
//    }

    Map<Integer, TreeNode> parents = new HashMap<>();
    List<Integer> ans2 = new ArrayList<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        //从root出发记录每个节点的父节点
        dfsParents(root);
        //从target出发，寻找所有深度为k的节点
        findAns(target, null, 0, k);
        return ans2;
    }

    private void findAns(TreeNode node, TreeNode from, int depth, int k) {
        if (node == null) {
            return;
        }
        if (depth == k) {
            ans2.add(node.val);
            return;
        }
        if (node.left != from) {
            findAns(node.left, node, depth + 1, k);
        }
        if (node.right != from) {
            findAns(node.right, node, depth + 1, k);
        }
        if (parents.get(node.val) != from) {
            findAns(parents.get(node.val), node, depth + 1, k);
        }
    }

    private void dfsParents(TreeNode node) {
        if (node.left != null) {
            parents.put(node.left.val, node);
            dfsParents(node.left);
        }
        if (node.right != null) {
            parents.put(node.right.val, node);
            dfsParents(node.right);
        }
    }


    /**
     * 引用计数法
     *
     * @param s
     * @return
     */
    public boolean areOccurrencesEqual(String s) {
        int[] arr = new int[26];
        for (char c : s.toCharArray()) {
            arr[c - 'a']++;
        }
        int first = -1;
        for (int num : arr) {
            if (num == 0) {
                continue;
            }
            if (first == -1) {
                first = num;
                continue;
            }
            if (first != num) {
                return false;
            }
        }
        return true;
    }

    /**
     * 引用计数法+双指针
     *
     * @param s
     * @return
     */
    public boolean areOccurrencesEqual2(String s) {
        int[] arr = new int[26];
        for (char c : s.toCharArray()) {
            arr[c - 'a']++;
        }
        int left = 0, right = arr.length - 1;
        while (left < right) {
            if (arr[left] == 0) {
                left++;
            } else if (arr[right] == 0) {
                right--;
            } else {
                if (arr[left] == arr[right]) {
                    left++;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 1952. 三除数
     *
     * @param n
     * @return
     */
    public boolean isThree(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (n % i == 0) {
                count++;
            }
            if (count == 3 && i != n) {
                return false;
            }
        }
        return count == 3;

    }

    /**
     * 611. 有效三角形的个数
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] > nums[k]) {
                        count++;
                        continue;
                    }
                    break;
                }
            }
        }
        return count;
    }

    /**
     * 611. 有效三角形的个数 双指针
     *
     * @param nums
     * @return
     */
    public int triangleNumber2(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int l = 0, r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    res += r - l;
                    r--;
                } else {
                    l++;
                }
            }
        }
        return res;
    }

    /**
     * 802. 找到最终的安全状态
     *
     * @param graph
     * @return
     */
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> newGraph = new ArrayList<>();
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) {
            newGraph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                newGraph.get(graph[i][j]).add(i);
            }
            indeg[i] = graph[i].length;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int x : newGraph.get(cur)) {
                indeg[x]--;
                if (indeg[x] == 0) {
                    queue.offer(x);
                }
            }
        }

        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                ret.add(i);
            }
        }
        return ret;
    }


    /**
     * 802. 找到最终的安全状态
     *
     * @param graph
     * @return
     */
    public List<Integer> eventualSafeNodes2(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (safe(graph, color, i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    private boolean safe(int[][] graph, int[] color, int x) {
        if (color[x] > 0) {
            return color[x] == 2;
        }
        color[x] = 1;
        for (int i : graph[x]) {
            if (!safe(graph, color, i)) {
                return false;
            }
        }
        color[x] = 2;
        return true;
    }

    /**
     * 847. 访问所有节点的最短路径
     *
     * @param graph
     * @return
     */
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        Queue<int[]> quque = new LinkedList<int[]>();
        boolean[][] seen = new boolean[n][1 << n];
        for (int i = 0; i < n; i++) {
            quque.offer(new int[]{i, 1 << i, 0});
            seen[i][1 << i] = true;
        }
        int ans = 0;
        while (!quque.isEmpty()) {
            int[] tuple = quque.poll();
            int u = tuple[0], mask = tuple[1], dist = tuple[2];
            if (mask == (1 << n) - 1) {
                ans = dist;
                break;
            }
            int[] ints = graph[u];
            for (int v : ints) {
                int maskV = mask | (1 << v);
                if (!seen[v][maskV]) {
                    quque.offer(new int[]{v, maskV, dist + 1});
                    seen[v][maskV] = true;
                }
            }
        }
        return ans;
    }

    int INF = 0x3f3f3f3f;

    /**
     * 847. 访问所有节点的最短路径
     *
     * @param graph
     * @return
     */
    public int shortestPathLength2(int[][] graph) {
        return 0;
    }

    /**
     * 313. 超级丑数
     *
     * @param n
     * @param primes
     * @return
     */
    public int nthSuperUglyNumber(int n, int[] primes) {
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        set.add(1L);
        priorityQueue.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long current = priorityQueue.poll();
            ugly = (int) current;
            for (int prime : primes) {
                long next = current * prime;
                if (set.add(next)) {
                    priorityQueue.offer(next);
                }
            }
        }
        return ugly;
    }

    /**
     * 313. 超级丑数 动态规划
     *
     * @param n
     * @param primes
     * @return
     */
    public int nthSuperUglyNumber2(int n, int[] primes) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int m = primes.length;
        int[] points = new int[m];
        Arrays.fill(points, 1);
        for (int i = 2; i <= n; i++) {
            int[] nums = new int[m];
            int minNum = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                nums[j] = dp[points[j]] * primes[j];
                minNum = Math.min(minNum, nums[j]);
            }
            dp[i] = minNum;
            for (int k = 0; k < m; k++) {
                if (minNum == nums[k]) {
                    points[k]++;
                }
            }
        }
        return dp[n];
    }

    /**
     * 313. 超级丑数 使用treeset
     *
     * @param n
     * @param primes
     * @return
     */
    public int nthSuperUglyNumber3(int n, int[] primes) {
        TreeSet<Long> treeSet = new TreeSet<>();
        treeSet.add(1L);
        for (int i = 1; i < n; i++) {
            Long min = treeSet.pollFirst();
            for (int prime : primes) {
                treeSet.add(prime * min);
            }
        }
        return Math.toIntExact(treeSet.pollFirst());
    }

    /**
     * 455. 分发饼干
     *
     * @param g
     * @param s
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gIndex = 0;
        int sIndex = 0;
        int count = 0;
        while (gIndex < g.length && sIndex < s.length) {
            if (g[gIndex] <= s[sIndex]) {
                gIndex++;
                sIndex++;
                count++;
                continue;
            }
            sIndex++;

        }
        return count;
    }

    /**
     * 413. 等差数列划分
     *
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int d = nums[0] - nums[1], t = 0;
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i - 1] - nums[i] == d) {
                t++;
            } else {
                d = nums[i - 1] - nums[i];
                t = 0;
            }
            ans += t;
        }
        return ans;
    }

    /**
     * 413. 等差数列划分 动态规划
     *
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlicesdp(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        int dp = 0, ans = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                ans += ++dp;
            } else {
                dp = 0;
            }
        }
        return ans;
    }

    /**
     * 135. 分发糖果
     *
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        int[] perCount = new int[ratings.length];
        perCount[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                perCount[i] = perCount[i - 1] + 1;
            } else if (ratings[i] == ratings[i - 1]) {
                perCount[i] = perCount[i - 1];
            } else {
                perCount[i] = 1;
            }
        }
        System.out.println(Arrays.toString(perCount));
        perCount[ratings.length - 1] = 1;
        int ans = 0;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                perCount[i] = Math.max(perCount[i + 1] + 1, perCount[i]);
            } else if (ratings[i] == ratings[i + 1]) {
                perCount[i] = Math.max(perCount[i + 1], perCount[i]);
            } else {
                perCount[i] = 1;
            }
            ans += perCount[i];
        }
        System.out.println(Arrays.toString(perCount));
        return ans;
    }

    /**
     * 135. 分发糖果
     *
     * @param ratings
     * @return
     */
    public int candy2(int[] ratings) {
        int[] perCount = new int[ratings.length];
        perCount[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                perCount[i] = perCount[i - 1] + 1;
            } else if (ratings[i] == ratings[i - 1]) {
                perCount[i] = perCount[i - 1];
            } else {
                perCount[i] = 1;
            }
        }
        System.out.println(Arrays.toString(perCount));
        perCount[ratings.length - 1] = 1;
        int ans = 0;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                perCount[i] = Math.max(perCount[i + 1] + 1, perCount[i]);
            } else if (ratings[i] == ratings[i + 1]) {
                perCount[i] = Math.max(perCount[i + 1], perCount[i]);
            } else {
                perCount[i] = 1;
            }
            ans += perCount[i];
        }
        System.out.println(Arrays.toString(perCount));
        return ans;
    }


    /**
     * 446. 等差数列划分 II - 子序列
     *
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlices2(int[] nums) {
        int ans = 0;
        int n = nums.length;
        Map<Long, Integer>[] map = new Map[n];
        for (int i = 0; i < n; i++) {
            map[i] = new HashMap<>();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long d = 1L * nums[i] - nums[j];
                int cnt = map[j].getOrDefault(d, 0);
                ans += cnt;
                map[i].put(d, map[i].getOrDefault(d, 0) + cnt + 1);
            }
        }
        return ans;

    }

    /**
     * 435. 无重叠区间
     *
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
        for (int[] interval : intervals) {
            System.out.println(Arrays.toString(interval));
        }

        int n = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] >= right) {
                ans++;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }

    /**
     * 516. 最长回文子序列 dp
     *
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    /**
     * 605. 种花问题
     *
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int len = flowerbed.length - 1, i = 0;
        while (i <= len) {
            boolean preFlag = i == 0 ? true : flowerbed[i - 1] == 0;
            if (!preFlag) {
                i++;
                continue;
            }
            boolean curFlag = flowerbed[i] == 0;
            if (!curFlag) {
                i += 2;
                continue;
            }
            boolean nextFlag = i == len ? true : flowerbed[i + 1] == 0;
            if (!nextFlag) {
                i += 2;
                continue;
            }
            flowerbed[i] = 1;
            i++;
        }
        return n <= count;
    }

    /**
     * 5843. 作为子字符串出现在单词中的字符串数目
     *
     * @param patterns
     * @param word
     * @return
     */
    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        for (String pattern : patterns) {
            if (word.contains(pattern)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 1137. 第 N 个泰波那契数
     *
     * @param n
     * @return
     */
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n < 3) return 1;
        if (n < 4) return 2;
        return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
    }

    /**
     * 526. 优美的排列
     *
     * @param n
     * @return
     */
    public int countArrangement(int n) {
        int mask = 1 << n;
        int[][] f = new int[n + 1][mask];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //枚举所有的状态
            for (int state = 0; state < mask; state++) {
                //枚举位置i(最后以为)选的数值是k
                for (int k = 1; k <= n; k++) {
                    //首先k在state中必是1
                    if (((state >> (k - 1)) & 1) == 0) continue;
                    //数值k与位置i之间满足任一整除关系
                    if (k % i != 0 && i % k != 0) continue;
                    //state & (~(1 << (k - 1))) 代表将state中数值k的位置置零
                    f[i][state] += f[i - 1][state & (~(1 << (k - 1)))];
                }
            }
        }
        return f[n][mask - 1];
    }

    /**
     * 1961. 检查字符串是否为数组前缀
     *
     * @param s
     * @param words
     * @return
     */
    public boolean isPrefixString(String s, String[] words) {
        StringBuilder sb = new StringBuilder();
        int k = s.length();
        for (String word : words) {
            sb.append(word);
            if (sb.length() == k && s.equals(sb.toString())) {
                return true;
            }
        }
        return false;
    }

    /**
     * 1957. 删除字符使字符串变好
     *
     * @param s
     * @return
     */
    public String makeFancyString(String s) {
        if (s == null || s.length() < 3) return s;
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        char preChar = chars[0];
        sb.append(preChar);
        int curCount = 1;
        for (int i = 1; i < chars.length; i++) {
            if (preChar == chars[i]) {
                curCount++;
            } else {
                preChar = chars[i];
                curCount = 1;
            }
            if (curCount >= 3) {
                continue;
            }
            sb.append(chars[i]);
        }
        return sb.toString();
    }

    /**
     * 551. 学生出勤记录 I
     *
     * @param s
     * @return
     */
    public boolean checkRecord(String s) {
        char[] chars = s.toCharArray();
        int lCount = chars[0] == 'L' ? 1 : 0;
        int aCount = chars[0] == 'A' ? 1 : 0;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == 'A') {
                aCount++;
                if (aCount >= 2) {
                    return false;
                }
            } else if (chars[i] == 'L') {
                lCount++;
                if (lCount >= 3) {
                    return false;
                }
                continue;
            }
            lCount = 0;
        }
        return true;
    }

    public static BigDecimal multiSum(BigDecimal start, BigDecimal end, BigDecimal rate) {
        BigDecimal profits = new BigDecimal("0");
        int count = 0;
        System.out.println("起始价 " + start + ",目标价 " + end + ",利润 " + profits);
        while (start.compareTo(end) <= 0) {
            start = start.multiply(BigDecimal.ONE.add(rate));
            profits = profits.add(start.multiply(new BigDecimal("0.016")));
            count++;
        }
        System.out.println("起始价 " + start.setScale(2, BigDecimal.ROUND_DOWN)
                + ",目标价 " + end.setScale(2).setScale(2, BigDecimal.ROUND_DOWN)
                + ",加价次数 " + count
                + ",利润 " + profits.setScale(2, BigDecimal.ROUND_DOWN));
        return profits;
    }

    /**
     * 552. 学生出勤记录 II
     *
     * @param n
     * @return
     */
    public int checkRecord(int n) {
        final int MOD = 10_0000_0007;
        int[][][] dp = new int[n + 1][2][3];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            //以P结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
                }
            }
            //以A结尾的数量
            for (int k = 0; k <= 2; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
            }
            //以L结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[n][j][k]) % MOD;
            }
        }
        return sum;
    }

    /**
     * 552. 学生出勤记录 II
     *
     * @param n
     * @return
     */
    public int checkRecord2(int n) {
        final int MOD = 10_0000_0007;
        int[][] dp = new int[2][3];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int[][] dpNew = new int[2][3];
            //以P结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= 2; k++) {
                    dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
                }
            }
            //以A结尾的数量
            for (int k = 0; k <= 2; k++) {
                dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
            }
            //以L结尾的数量
            for (int j = 0; j <= 1; j++) {
                for (int k = 1; k <= 2; k++) {
                    dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
                }
            }
            dp = dpNew;
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[j][k]) % MOD;
            }
        }
        return sum;
    }

    /**
     * 剑指 Offer II 032. 有效的变位词
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] count = new char[123];
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        boolean flag = true;
        for (int i = 0; i < sChars.length; i++) {
            count[sChars[i]]++;
            count[tChars[i]]--;
            if (sChars[i] != tChars[i]) {
                flag = false;
            }
        }
        if (flag) return true;
        for (int i = 97; i < count.length; i++) {
            if (count[i] == 0) {
                continue;
            }
            return false;
        }
        return true;

    }

    /**
     * 1844. 将所有数字用字符替换
     *
     * @param s
     * @return
     */
    public String replaceDigits(String s) {
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if ((i & 1) == 0) {
                sb.append(chars[i]);
            } else {
                sb.append((char) (chars[i - 1] + chars[i]));
                System.out.println(chars[i - 1] + chars[i]);
                System.out.println((char) (chars[i - 1] + chars[i]));
            }
        }
        return sb.toString();
    }

    /**
     * 345. 反转字符串中的元音字母
     *
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        Set<Character> characterSet = Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        char[] chars = s.toCharArray();
        int startIndex = 0;
        int endIndex = chars.length - 1;
        while (startIndex < endIndex) {
            if (!characterSet.contains(chars[startIndex])) {
                startIndex++;
            }
            if (!characterSet.contains(chars[endIndex])) {
                endIndex--;
            }
            if (!characterSet.contains(chars[startIndex]) && !characterSet.contains(chars[endIndex])) {
                char temp = chars[startIndex];
                chars[startIndex] = chars[endIndex];
                chars[endIndex] = temp;
                startIndex++;
                endIndex--;
            }
        }
        return new String(chars);
    }

    /**
     * 541. 反转字符串 II
     *
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int n = s.length();
        for (int l = 0; l < n; l = l + 2 * k) {
            int r = l + k - 1;
            reverse(cs, l, Math.min(r, n - 1));
        }
        return String.valueOf(cs);
    }

    void reverse(char[] cs, int l, int r) {
        while (l < r) {
            char c = cs[l];
            cs[l] = cs[r];
            cs[r] = c;
            l++;
            r--;
        }
    }

    /**
     * 748. 最短补全词
     *
     * @param licensePlate
     * @param words
     * @return
     */
    public String shortestCompletingWord(String licensePlate, String[] words) {
        String lowerCase = licensePlate.toLowerCase();
        char[] chars = lowerCase.toCharArray();
        int length = Integer.MAX_VALUE;
        String result = null;
        for (String word : words) {
            if (length > word.length() && aContainsB(chars, word)) {
                result = word;
                length = word.length();
            }
        }
        return result;
    }

    private boolean aContainsB(char[] licensePlateChars, String b) {
        Map<Character, Integer> bCharsMap = new HashMap<>();
        for (char aChar : b.toCharArray()) {
            bCharsMap.put(aChar, bCharsMap.getOrDefault(aChar, 0) + 1);
        }
        for (char licensePlateChar : licensePlateChars) {
            if (licensePlateChar < 'a' || licensePlateChar > 'z') {
                continue;
            }
            System.out.print(licensePlateChars);
            if (!bCharsMap.containsKey(licensePlateChar) || bCharsMap.get(licensePlateChar) < 1) {
                return false;
            }
            bCharsMap.put(licensePlateChar, bCharsMap.getOrDefault(licensePlateChar, 0) - 1);
        }
        return true;
    }

    /**
     * 1646. 获取生成数组中的最大值
     *
     * @param n
     * @return
     */
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        int[] ints = new int[n + 1];
        ints[0] = 0;
        ints[1] = 1;
        int max = 1;
        for (int i = 2; i <= n; i++) {
            if ((i & 1) == 1) {
                int preIndex = (i - 1) >> 1;
                ints[i] = ints[preIndex] + ints[preIndex + 1];
            } else {
                ints[i] = ints[i >> 1];
            }
            max = Math.max(max, ints[i]);
        }
        return max;
    }

    /**
     * 787. K 站中转内最便宜的航班
     *
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 10000 * 101 + 1;
        int[][] f = new int[k + 2][n];
        for (int i = 0; i < k + 2; i++) {
            Arrays.fill(f[i], INF);
        }
        f[0][src] = 0;
        for (int t = 1; t <= k + 1; t++) {
            for (int[] flight : flights) {
                int j = flight[0], i = flight[1], cost = flight[2];
                f[t][i] = Math.min(f[t][i], f[t - 1][j] + cost);
            }
        }
        int ans = INF;
        for (int i = 1; i <= k + 1; i++) {
            ans = Math.min(ans, f[i][dst]);
        }
        return ans == INF ? -1 : ans;
    }

    /**
     * 1974. 使用特殊打字机键入单词的最少时间
     *
     * @param word
     * @return
     */
    public int minTimeToType(String word) {
        int count = 0;
        char[] chars = word.toCharArray();
        char pre = 'a';
        for (int i = 0; i < chars.length; i++) {
            int abs = chars[i] >= pre ? chars[i] - pre : pre - chars[i];
            count += abs >= 13 ? 26 - abs : abs;
            pre = chars[i];
        }
        count += chars.length;
        return count;
    }

    /**
     * 797. 所有可能的路径
     *
     * @param graph
     * @return
     */
    public List<List<Integer>> allPathsSourceTargetDFS(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int[] ints : graph) {
            for (int anInt : ints) {
                queue.add(anInt);
            }
        }
        while (!queue.isEmpty()) {

        }
        return result;
    }

    /**
     * 881. 救生艇
     *
     * @param people
     * @param limit
     * @return
     */
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int startIndex = 0;
        int endIndex = people.length - 1;
        int count = 0;
        while (startIndex < endIndex) {

            if (people[startIndex] + people[endIndex] <= limit) {
                startIndex++;
            }
            endIndex--;
            ++count;
        }
        return count;
    }

    /**
     * 1109. 航班预订统计
     *
     * @param bookings
     * @param n
     * @return
     */
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] result = new int[n];
        for (int i = 0; i < bookings.length; i++) {
            int startIndex = bookings[i][0];
            int endIndex = bookings[i][1];
            int seats = bookings[i][2];
            while (startIndex < endIndex) {
                result[startIndex - 1] += seats;
                result[endIndex - 1] += seats;
                startIndex++;
                endIndex--;
            }
            if (startIndex == endIndex) {
                result[endIndex - 1] += seats;
            }
        }
        return result;
    }

    /**
     * 1109. 航班预订统计  diffDivide
     *
     * @param bookings
     * @param n
     * @return
     */
    public int[] corpFlightBookings2(int[][] bookings, int n) {
        int[] c = new int[n + 1];
        for (int[] booking : bookings) {
            c[booking[0] - 1] += booking[2];
            c[booking[1]] -= booking[2];
        }
        int[] ans = new int[n];
        ans[0] = c[0];
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] + ans[i];
        }
        return ans;
    }

    /**
     * 剑指 Offer 22. 链表中倒数第k个节点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode tempNode = head;
        int count = 0;
        while (tempNode != null) {
            tempNode = tempNode.next;
            count++;
        }
        while (count-- > k) {
            head = head.next;
        }
        tempNode = head.next;
        return tempNode;

    }

    /**
     * 面试题 17.14. 最小K个数
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = arr[i];
        }
        return arr;
    }

    /**
     * 面试题 17.14. 最小K个数
     *
     * @param arr
     * @param k
     * @return
     */
    public int[] smallestK2(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) return vec;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            if (priorityQueue.peek() > arr[i]) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            vec[i] = priorityQueue.poll();
        }
        return vec;
    }

    /**
     * 704. 二分查找
     *
     * @param nums
     * @param target
     * @return
     */
    public int search3(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int cur = (l + r) >> 1;
            if (nums[cur] < target) {
                l = cur + 1;
            } else if (nums[cur] > target) {
                r = cur - 1;
            } else {
                return cur;
            }
        }
        return -1;
    }

    public int countQuadruplets(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int a = 0; a < n; a++) {
            for (int b = a + 1; b < n; b++) {
                for (int c = b + 1; c < n; c++) {
                    boolean flag = false;
                    for (int d = c + 1; d < n; d++) {
                        int preSum = nums[a] + nums[b] + nums[c];
                        if (preSum == nums[d]) {
                            res++;
                            flag = true;
                            continue;
                        }
                        if (flag) {
                            break;
                        }
                    }
                }
            }
        }
        return res;
    }

    /**
     * 1221. 分割平衡字符串
     *
     * @param s
     * @return
     */
    public int balancedStringSplit(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        int lCount = 0, rCount = 0;
        for (char aChar : chars) {
            if (aChar == 'R') {
                lCount++;
            }
            if (aChar == 'L') {
                rCount++;
            }
            if (lCount == rCount) {
                count++;
            }
        }
        return count;
    }

    /**
     * 1991. 找到数组的中间位置
     *
     * @param nums
     * @return
     */
    public int findMiddleIndex(int[] nums) {
        int[] arrSum = new int[nums.length + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            arrSum[i] = nums[i] + arrSum[i + 1];
        }
        int afterSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (afterSum == arrSum[i + 1]) {
                return i;
            }
            afterSum += nums[i];
        }
        return -1;
    }

    /**
     * 68. 文本左右对齐
     *
     * @param words
     * @param maxWidth
     * @return
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int n = words.length;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; ) {
            // list 装载当前行的所有 word
            list.clear();
            list.add(words[i]);
            int cur = words[i++].length();
            while (i < n && cur + 1 + words[i].length() <= maxWidth) {
                cur += 1 + words[i].length();
                list.add(words[i++]);
            }

            // 当前行为最后一行，特殊处理为左对齐
            if (i == n) {
                StringBuilder sb = new StringBuilder(list.get(0));
                for (int k = 1; k < list.size(); k++) {
                    sb.append(" ").append(list.get(k));
                }
                while (sb.length() < maxWidth) sb.append(" ");
                ans.add(sb.toString());
                break;
            }

            // 如果当前行只有一个 word，特殊处理为左对齐
            int cnt = list.size();
            if (cnt == 1) {
                String str = list.get(0);
                while (str.length() != maxWidth) str += " ";
                ans.add(str);
                continue;
            }

            /**
             * 其余为一般情况
             * wordWidth : 当前行单词总长度;
             * spaceWidth : 当前行空格总长度;
             * spaceItem : 往下取整后的单位空格长度
             */
            int wordWidth = cur - (cnt - 1);
            int spaceWidth = maxWidth - wordWidth;
            int spaceItemWidth = spaceWidth / (cnt - 1);
            String spaceItem = "";
            for (int k = 0; k < spaceItemWidth; k++) spaceItem += " ";
            StringBuilder sb = new StringBuilder();
            for (int k = 0, sum = 0; k < cnt; k++) {
                String item = list.get(k);
                sb.append(item);
                if (k == cnt - 1) break;
                sb.append(spaceItem);
                sum += spaceItemWidth;
                // 剩余的间隙数量（可填入空格的次数）
                int remain = cnt - k - 1 - 1;
                // 剩余间隙数量 * 最小单位空格长度 + 当前空格长度 < 单词总长度，则在当前间隙多补充一个空格
                if (remain * spaceItemWidth + sum < spaceWidth) {
                    sb.append(" ");
                    sum++;
                }
            }
            ans.add(sb.toString());
        }
        return ans;
    }

    private void combine(int[][] trucks, int target) {
        List<List<Integer>> list = new ArrayList<>();
        int minCount = 0;
        int idx = trucks.length - 1;
        int sum = 0;
        while (idx >= 0) {
            int[] truck = trucks[idx];
            boolean flag = false;
            for (int i = 0; i <= truck[1]; i++) {
                sum += truck[0];
                if (sum >= target) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
            idx--;
        }

    }

    private void combineDFS(List<List<Integer>> list, int curr, int count, int used, int ids) {
        if (used == 1) {

        }
    }

    /**
     * 1894. 找到需要补充粉笔的学生编号
     *
     * @param chalk
     * @param k
     * @return
     */
    public int chalkReplacer(int[] chalk, int k) {
        int sum = 0;
        for (int i : chalk) {
            sum += i;
        }
        int mod = k % sum;
        for (int i = 0; i < chalk.length; i++) {
            if (mod < chalk[i]) {
                return i;
            }
            mod -= chalk[i];
        }
        return -1;
    }

    // 创建一个可重用固定个数的线程池
    ExecutorService fixedThreadPool = Executors.newFixedThreadPool(3);


//    public static void main(String[] args) {
//        //初始化商品信息
//        List<GoodsInfo> goodsInfos = getGoodsInfos();
//        //对获取到的商品信息进行排序
//        List<GoodsInfo> sortGoodsList = getSortGoods(goodsInfos);
//        sortGoodsList.forEach(goodsInfo -> System.out.println(goodsInfo));
//        //建立一个全局的商品信息
//        Map<String, GoodsInfo> allGoodsMap = sortGoodsList.stream().collect(Collectors.toConcurrentMap(GoodsInfo::getId, Function.identity()));
//        //获取对应所有的用户
//        List<UserInfo> userInfos = getUserInfos();
//
//    }

    private static List<GoodsInfo> getGoodsInfos() {
        GoodsInfo goodsInfo1 = new GoodsInfo("1", BigDecimal.valueOf(2.2), true);
        GoodsInfo goodsInfo2 = new GoodsInfo("2", BigDecimal.valueOf(3.5), true);
        GoodsInfo goodsInfo3 = new GoodsInfo("3", BigDecimal.valueOf(4.4), true);
        GoodsInfo goodsInfo4 = new GoodsInfo("4", BigDecimal.valueOf(4.5), false);
        GoodsInfo goodsInfo5 = new GoodsInfo("5", BigDecimal.valueOf(3.4), true);
        GoodsInfo goodsInfo6 = new GoodsInfo("6", BigDecimal.valueOf(6.4), true);
        GoodsInfo goodsInfo7 = new GoodsInfo("7", BigDecimal.valueOf(5.3), true);
        GoodsInfo goodsInfo8 = new GoodsInfo("8", BigDecimal.valueOf(5.2), true);
        GoodsInfo goodsInfo9 = new GoodsInfo("9", BigDecimal.valueOf(6.1), true);
        GoodsInfo goodsInfo10 = new GoodsInfo("10", BigDecimal.valueOf(6.3), true);
        GoodsInfo goodsInfo11 = new GoodsInfo("11", BigDecimal.valueOf(7.2), true);
        List<GoodsInfo> list = new ArrayList<>();
        list.add(goodsInfo1);
        list.add(goodsInfo2);
        list.add(goodsInfo3);
        list.add(goodsInfo4);
        list.add(goodsInfo5);
        list.add(goodsInfo6);
        list.add(goodsInfo7);
        list.add(goodsInfo8);
        list.add(goodsInfo9);
        list.add(goodsInfo10);
        list.add(goodsInfo11);
        return list;
    }

    /**
     * 对获取到的商品信息进行排序
     *
     * @param goodsInfos
     */
    public static List<GoodsInfo> getSortGoods(List<GoodsInfo> goodsInfos) {
        //获取可抢单的商品，且跟据价格由高到底排序
        List<GoodsInfo> goodsInfoList = goodsInfos.stream().filter(GoodsInfo::isUsed).sorted(Comparator.comparing(GoodsInfo::getPrice).reversed()).collect(Collectors.toList());
        return goodsInfoList;
    }

    private static List<UserInfo> getUserInfos() {
        UserInfo userInfo1 = new UserInfo("1", BigDecimal.valueOf(2), BigDecimal.valueOf(3));
        UserInfo userInfo2 = new UserInfo("2", BigDecimal.valueOf(2), BigDecimal.valueOf(3));
        UserInfo userInfo3 = new UserInfo("3", BigDecimal.valueOf(3), BigDecimal.valueOf(4));
        UserInfo userInfo4 = new UserInfo("4", BigDecimal.valueOf(3), BigDecimal.valueOf(4));
        UserInfo userInfo5 = new UserInfo("5", BigDecimal.valueOf(4), BigDecimal.valueOf(5));
        UserInfo userInfo6 = new UserInfo("6", BigDecimal.valueOf(4), BigDecimal.valueOf(5));
        UserInfo userInfo7 = new UserInfo("7", BigDecimal.valueOf(5), BigDecimal.valueOf(6));
        UserInfo userInfo8 = new UserInfo("8", BigDecimal.valueOf(6), BigDecimal.valueOf(7));
        UserInfo userInfo9 = new UserInfo("9", BigDecimal.valueOf(6), BigDecimal.valueOf(7));
        UserInfo userInfo10 = new UserInfo("10", BigDecimal.valueOf(7), BigDecimal.valueOf(8));
        List<UserInfo> list = new ArrayList<>();
        list.add(userInfo1);
        list.add(userInfo2);
        list.add(userInfo3);
        list.add(userInfo4);
        list.add(userInfo5);
        list.add(userInfo6);
        list.add(userInfo7);
        list.add(userInfo8);
        list.add(userInfo9);
        list.add(userInfo10);
        return list;
    }


    private static class UserInfo {
        private String id;

        private BigDecimal minPrice;

        private BigDecimal maxPrice;

        public UserInfo(String id, BigDecimal minPrice, BigDecimal maxPrice) {
            this.id = id;
            this.minPrice = minPrice;
            this.maxPrice = maxPrice;
        }

        public String getId() {
            return id;
        }

        public void setId(String id) {
            this.id = id;
        }

        public BigDecimal getMinPrice() {
            return minPrice;
        }

        public void setMinPrice(BigDecimal minPrice) {
            this.minPrice = minPrice;
        }

        public BigDecimal getMaxPrice() {
            return maxPrice;
        }

        public void setMaxPrice(BigDecimal maxPrice) {
            this.maxPrice = maxPrice;
        }
    }


    private static class GoodsInfo {
        private String id;
        private BigDecimal price;
        private boolean isUsed;

        public GoodsInfo(String id, BigDecimal price, boolean isUsed) {
            this.id = id;
            this.price = price;
            this.isUsed = isUsed;
        }

        public boolean isUsed() {
            return isUsed;
        }

        public void setUsed(boolean used) {
            isUsed = used;
        }

        public String getId() {
            return id;
        }

        public void setId(String id) {
            this.id = id;
        }

        public BigDecimal getPrice() {
            return price;
        }

        public void setPrice(BigDecimal price) {
            this.price = price;
        }

        @Override
        public String toString() {
            return "GoodsInfo{" +
                    "id='" + id + '\'' +
                    ", price=" + price +
                    ", isUsed=" + isUsed +
                    '}';
        }
    }

    /**
     * 447. 回旋镖的数量
     *
     * @param points
     * @return
     */
    public int numberOfBoomerangs(int[][] points) {
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                int dst = (int) (Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));
                map.put(dst, map.getOrDefault(dst, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int m = entry.getValue();
                ans += (m - 1) * m;
            }
        }
        return ans;
    }

    /**
     * 524. 通过删除字母匹配到字典里最长单词
     *
     * @param s
     * @param dictionary
     * @return
     */
    public String findLongestWord(String s, List<String> dictionary) {
        char[] chars = s.toCharArray();
        String result = "";
        for (String s1 : dictionary) {
            char[] charArray = s1.toCharArray();
            if (charArray.length > chars.length) {
                continue;
            }
            int charsIndex = 0, charArrayIndex = 0;
            while (charArrayIndex < charArray.length && charsIndex < chars.length) {
                if (charArray[charArrayIndex] == chars[charsIndex]) {
                    charArrayIndex++;
                }
                charsIndex++;
            }
            if (charArrayIndex != charArray.length) {
                continue;
            }
            if (charArray.length > result.length() || (charArray.length == result.length() && s1.compareTo(result) < 0)) {
                result = s1;
            }
        }
        return result;
    }

    /**
     * 162. 寻找峰值
     *
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) return nums[0];
        int left = -1;
        int right = 1;
        int cur = 0;
        while (cur < nums.length) {
            if (left == -1) {
                if (nums[cur] > nums[right]) {
                    return cur;
                }
                left++;
                cur++;
                right++;
                continue;
            }
            if (right == nums.length) {
                if (nums[cur] > nums[left]) {
                    return cur;
                }
                left++;
                cur++;
                right++;
                continue;
            }
            if (nums[cur] > nums[left] && nums[cur] > nums[right]) {
                return cur;
            }

        }
        return -1;
    }

    /**
     * 2001. 可互换矩形的组数
     *
     * @param rectangles
     * @return
     */
    public long interchangeableRectangles(int[][] rectangles) {
        Map<Integer, Integer> map = new HashMap<>(rectangles.length);
        for (int[] rectangle : rectangles) {
            int key = rectangle[0] / rectangle[1];
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ans += (entry.getValue() - 1) * entry.getValue();
        }
        return ans;
    }

    /**
     * 36. 有效的数独
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        int count = 1 << 10;
        int first = count, second = count, third = count;
        for (int i = 0; i < board.length; i++) {
            int countRow = count;
            int countCol = count;
            if (i % 3 == 0) {
                first = count;
                second = count;
                third = count;
            }
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] != '.') {
                    int tempRow = 1 << (board[i][j] - 48);
                    if ((countRow & tempRow) > 1) {
                        return false;
                    }
                    countRow |= tempRow;
                    if (j < 3) {
                        if ((first & tempRow) > 1) {
                            return false;
                        }
                        first |= tempRow;
                        continue;
                    }
                    if (j < 6) {
                        if ((second & tempRow) > 1) {
                            return false;
                        }
                        second |= tempRow;
                        continue;
                    }
                    if (j < 9) {
                        if ((third & tempRow) > 1) {
                            return false;
                        }
                        third |= tempRow;
                    }
                }
                if (board[j][i] != '.') {
                    int tempCol = 1 << (board[j][i] - 48);
                    System.out.println(board[j][i] - 48);
                    if ((countCol & tempCol) > 1) {
                        System.out.println("------------ countCol");
                        return false;
                    }
                    countCol |= tempCol;
                }
            }

        }
        return true;
    }

    /**
     * 36. 有效的数独
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku2(char[][] board) {
        Map<Integer, Set<Integer>> row = new HashMap<>(), col = new HashMap<>(), area = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            row.put(i, new HashSet<>());
            col.put(i, new HashSet<>());
            area.put(i, new HashSet<>());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                int u = c - '0';
                int idx = i / 3 * 3 + j / 3;
                if (row.get(i).contains(u) || col.get(j).contains(u) || area.get(idx).contains(u)) return false;
                row.get(i).add(u);
                col.get(j).add(u);
                area.get(idx).add(u);
            }
        }
        return true;
    }

    /**
     * 36. 有效的数独
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku3(char[][] board) {
        boolean[][] row = new boolean[10][10], col = new boolean[10][10], area = new boolean[10][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                int u = c - '0';
                int index = i / 3 * 3 + j / 3;
                if (row[i][u] || col[j][u] || area[index][u]) return false;
                row[i][u] = true;
                col[j][u] = true;
                area[index][u] = true;
            }
        }
        return true;
    }

    /**
     * 36. 有效的数独
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku4(char[][] board) {
        int[] row = new int[10], col = new int[10], area = new int[10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                int u = c - '0';
                int idx = i / 3 * 3 + j / 3;
                if (((row[i] >> u) & 1) == 1 || ((col[j] >> u) & 1) == 1 || ((area[idx] >> u) & 1) == 1) return false;
                row[i] |= (1 << u);
                row[j] |= (1 << u);
                row[idx] |= (1 << u);
            }
        }
        return true;
    }

    /**
     * 中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        inOrderDfs(root, list);
        return list;
    }

    private void inOrderDfs(TreeNode node, List<Integer> list) {
        if (node == null) return;
        inOrderDfs(node.left, list);
        list.add(node.val);
        inOrderDfs(node.right, list);
    }

    /**
     * 中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;

        }
        return list;
    }

    /**
     * 725. 分隔链表
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode[] splitListToParts(ListNode head, int k) {
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        int subLen = len / k;
        int per = len % k;
        ListNode[] result = new ListNode[k];
        temp = head;
        for (int i = 0; i < k && temp != null; i++) {
            result[i] = temp;
            int partSize = subLen + (i < per ? 1 : 0);
            for (int j = 1; j < partSize; j++) {
                temp = temp.next;
            }
            ListNode next = temp.next;
            temp.next = null;
            temp = next;
        }
        return result;
    }

    /**
     * 2. 两数相加
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        int tempValue = 0;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                temp.next = l2;
                int val = l2.val + tempValue;
                temp.next.val = val % 10;
                tempValue = val > 9 ? 1 : 0;
                temp = temp.next;
                l2 = l2.next;
                continue;
            }
            if (l2 == null) {
                temp.next = l1;
                int val = l1.val + tempValue;
                temp.next.val = val % 10;
                tempValue = val > 9 ? 1 : 0;
                temp = temp.next;
                l1 = l1.next;
                continue;
            }
            temp.next = l1;
            int val = l1.val + l2.val;
            temp.next.val = (val + tempValue) % 10;
            tempValue = val > 9 ? 1 : 0;
            temp = temp.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (tempValue > 0) {
            temp.next = new ListNode(tempValue);
        }
        return head.next;
    }

    /**
     * 326. 3的幂
     *
     * @param n
     * @return
     */
    public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        temp = head;
        ListNode result = new ListNode(-1);
        ListNode tempResult = result;
        while (temp != null) {
            if (len-- == n) {
                System.out.println(len);
                temp = temp.next;
                continue;
            }
            System.out.println("---" + len);
            ListNode listNode = new ListNode(temp.val);
            tempResult.next = listNode;
            temp = temp.next;
        }
        return result.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        temp = head;
        while (temp != null) {
            if (--len == n) {
                if (temp.next != null) {
                    temp.next = temp.next.next;
                    temp = temp.next.next;
                }
                temp = temp.next;
                continue;
            }
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        ListNode cur = dummy;
        for (int i = 1; i < len - n + 1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd4(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd5(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    /**
     * 21. 合并两个有序链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                cur.next = l2;
                break;
            }
            if (l2 == null) {
                cur.next = l1;
                break;
            }
            if (l1.val >= l2.val) {
                cur.next = l2;
                cur = l2;
                l2 = l2.next;
            } else {
                cur.next = l1;
                cur = l1;
                l1 = l1.next;
            }
        }
        return dummy.next;
    }

    /**
     * 430. 扁平化多级双向链表
     *
     * @param head
     * @return
     */
    public Node flatten(Node head) {
        Node dummy = new Node(0);
        dummy.next = head;

        while (head != null) {
            if (head.child == null) {
                head = head.next;
            } else {
                Node temp = head.next;
                Node chead = flatten(head.child);
                head.next = chead;
                chead.prev = head;
                head.child = null;
                while (head.next != null) head = head.next;
                head.next = temp;
                if (temp != null) temp.prev = head;
                head = temp;
            }

        }
        return dummy.next;
    }

    /**
     * 430. 扁平化多级双向链表
     *
     * @param head
     * @return
     */
    public Node flatten2(Node head) {
        flattenDFS(head);
        return head;
    }

    private Node flattenDFS(Node head) {
        Node last = head;
        while (head != null) {
            if (head.child == null) {
                last = head;
                head = head.next;
            } else {
                Node temp = head.next;
                Node childLast = flattenDFS(head.child);
                head.next = head.child;
                head.child.prev = head;
                head.child = null;
                if (childLast != null) childLast.next = temp;
                if (temp != null) temp.prev = childLast;
                last = head;
                head = childLast;
            }
        }
        return last;
    }

    /**
     * 430. 扁平化多级双向链表
     *
     * @param head
     * @return
     */
    public Node flatten3(Node head) {
        Node dummy = new Node(0);
        dummy.next = head;
        for (; head != null; head = head.next) {
            if (head.child != null) {
                Node temp = head.next;
                Node child = head.child;
                head.next = child;
                child.prev = head;
                head.child = null;
                Node last = head;
                while (last.next != null) last = last.next;
                last.next = temp;
                if (temp != null) temp.prev = last;
            }
        }
        return dummy.next;
    }

    /**
     * 剑指 Offer 52. 两个链表的第一个公共节点
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode dummy = new ListNode(-1);


        return dummy.next;
    }


    /**
     * 371. 两整数之和
     *
     * @param a
     * @param b
     * @return
     */
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }

    /**
     * 639. 解码方法 II
     *
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int mod = (int) 1e9 + 7;
        char[] cs = s.toCharArray();
        int n = cs.length;
        long[] f = new long[n];
        f[0] = cs[0] == '*' ? 9 : (cs[0] != '0' ? 1 : 0);
        for (int i = 1; i < n; i++) {
            char c = cs[i], prev = cs[i - 1];
            if (c == '*') {
                //cs[i] 作为一个单独的item
                f[i] += f[i - 1] * 9;
                //cs[i]与前一个字符共同作为一个item
                if (prev == '*') {
                    // 11-19 & 21-26
                    f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 15;
                } else {
                    int u = prev - '0';
                    if (u == 1) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 9;
                    } else if (u == 2) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 6;
                    }
                }
            } else {
                int t = c - '0';
                if (prev == '*') {
                    if (t == 0) {
                        f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                    } else {
                        //cs[i] 单独作为一个item
                        f[i] += f[i - 1];
                        //cd[i] 与前一个字符共同作为一个item
                        if (t <= 6) {
                            f[i] += (i - 2 >= 0 ? f[i - 2] : 1) * 2;
                        } else {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    }
                } else {
                    int u = prev - '0';
                    if (t == 0) {
                        if (u == 1 || u == 2) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    } else {
                        //cs[i]单独作为一个item
                        f[i] += f[i - 1];
                        //cs[i] 与前一个字符共同作为一个item
                        if (u == 1) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        } else if (u == 2 && t <= 6) {
                            f[i] += i - 2 >= 0 ? f[i - 2] : 1;
                        }
                    }
                }
            }
            f[i] %= mod;
        }
        return (int) f[n - 1];
    }

    /**
     * 5881. 增量元素之间的最大差值
     *
     * @param nums
     * @return
     */
    public int maximumDifference(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                ans = Math.max(ans, (nums[j] - nums[i]));
            }
        }
        return ans == 0 ? -1 : ans;
    }

    /**
     * 223. 矩形面积
     *
     * @param ax1
     * @param ay1
     * @param ax2
     * @param ay2
     * @param bx1
     * @param by1
     * @param bx2
     * @param by2
     * @return
     */
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int y = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - x * y;
    }

    /**
     * 203. 移除链表元素
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return head;
        return null;
    }

    /**
     * 187. 重复的DNA序列
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() < 10) return result;
        int startIndex = 0;
        int endIndex = 9;
        Set<String> set = new HashSet<>();
        int length = s.length();
        while (endIndex < length) {
            String substring = s.substring(startIndex++, endIndex++ + 1);
            if (set.contains(substring) && !result.contains(substring)) {
                result.add(substring);
            }
            set.add(substring);
        }
        return result;
    }

    /**
     * 187. 重复的DNA序列
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences2(String s) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0, l = 10, length = s.length() - l; i <= length; i++) {
            String substring = s.substring(i, i + l);
            map.put(substring, map.getOrDefault(substring, 0) + 1);
            if (map.get(substring) == 2) {
                result.add(substring);
            }
        }
        return result;
    }

    /**
     * 434. 字符串中的单词数
     *
     * @param s
     * @return
     */
    public int countSegments(String s) {
        if (s == null || s.length() == 0) return 0;
        int count = 0;
        boolean flag = true;
        s = s.trim();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ' && flag) {
                count++;
                flag = false;
            } else {
                flag = true;
            }
        }
        return count + 1;
    }

    /**
     * 1. 两数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff) && map.get(diff) != i) {
                result[0] = i;
                result[1] = map.get(diff);
                break;
            }
        }
        return result;
    }

    /**
     * 面试题 10.02. 变位词组
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String s = Arrays.toString(charArray);
            if (map.containsKey(s)) {
                List<String> list = map.get(s);
                list.add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(s, list);
            }
        }
        List<List<String>> result = new ArrayList<>();
        map.values().forEach(list -> result.add(list));
        return result;
    }

    /**
     * 441. 排列硬币
     *
     * @param n
     * @return
     */
    public int arrangeCoins(int n) {
        long l = 0, r = n;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if ((mid * (mid + 1) >> 1) <= n) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) r;
    }

    /**
     * 273. 整数转换英文表示
     *
     * @param num
     * @return
     */
    static String[] num2str_small = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
            "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    static String[] num2str_medium = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    static String[] num2str_large = {"Billion", "Million", "Thousand", ""};

    public String numberToWords(int num) {
        if (num == 0) return num2str_small[num];
        StringBuilder sb = new StringBuilder();
        for (int i = (int) 1e9, j = 0; i >= 1; i /= 1000, j++) {
            if (num < i) continue;
            sb.append(num2Str(num / i)).append(num2str_large[j]).append(" ");
            num %= i;
        }
        while (sb.charAt(sb.length() - 1) == ' ') sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    private String num2Str(int x) {
        StringBuilder sb = new StringBuilder();
        if (x >= 100) {
            sb.append(num2str_small[x / 100]).append(" Hundred ");
            x %= 100;
        }
        if (x >= 20) {
            sb.append(num2str_medium[x / 10]).append(" ");
            x %= 10;
        }
        if (x != 0) {
            sb.append(num2str_small[x]).append(" ");
        }
        return sb.toString();
    }

    /**
     * 2032. 至少在两个数组中出现的值
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @return
     */
    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        twoOutOfThree(nums1, map);
        twoOutOfThree(nums2, map);
        twoOutOfThree(nums3, map);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) result.add(entry.getKey());
        }
        return result;
    }

    private void twoOutOfThree(int[] nums1, Map<Integer, Integer> map) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums1) {
            if (set.contains(i)) continue;
            map.put(i, map.getOrDefault(i, 0) + 1);
            set.add(i);
        }
    }

    /**
     * 2032. 至少在两个数组中出现的值
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @return
     */
    public List<Integer> twoOutOfThree2(int[] nums1, int[] nums2, int[] nums3) {
        List<Integer> result = new ArrayList<>();
        int[] ints = new int[101];
        twoOutOfThree2(nums1, ints);
        twoOutOfThree2(nums2, ints);
        twoOutOfThree2(nums3, ints);
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] > 1) result.add(i);
        }
        return result;
    }

    /**
     * 2022. 将一维数组转变成二维数组
     *
     * @param original
     * @param m
     * @param n
     * @return
     */
    public int[][] construct2DArray(int[] original, int m, int n) {
        if (original.length != m * n) return new int[0][0];
        int[][] arr = new int[m][n];
        int index = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = original[index++];
            }
        }
        return arr;
    }

    private void twoOutOfThree2(int[] nums1, int[] arr) {
        int[] ints = new int[101];
        for (int i : nums1) {
            if (ints[i] > 0) continue;
            arr[i]++;
            ints[i]++;
        }
    }


    /**
     * 412. Fizz Buzz
     *
     * @param n
     * @return
     */
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            boolean threeFlag = i % 3 == 0;
            boolean fiveFlag = i % 5 == 0;
            if (threeFlag && fiveFlag) {
                list.add("FizzBuzz");
            } else if (threeFlag) {
                list.add("Fizz");
            } else if (fiveFlag) {
                list.add("Buzz");
            } else {
                list.add(Integer.toString(i));
            }
        }
        return list;
    }

    /**
     * 1. 两数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    /**
     * 剑指 Offer II 069. 山峰数组的顶部
     *
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid - 1] < arr[mid]) l = mid;
            else r = mid - 1;
        }
        return r;
    }

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        return 0;
    }

    /**
     * 2042. 检查句子中的数字是否递增
     *
     * @param s
     * @return
     */
    public boolean areNumbersAscending(String s) {
        String[] arr = s.split(" ");
        int pre = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].charAt(0) >= 'a') {
                continue;
            }
            int cur = Integer.valueOf(arr[i]);
            if (pre >= cur) return false;
            pre = cur;
        }
        return true;
    }

    /**
     * 66. 加一
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        int last = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int temp = digits[i] + last;
            if (temp > 9) {
                last = 1;
                digits[i] += temp % 10;
            } else {
                digits[i] += temp % 10;
                return digits;
            }
        }
        int[] ints = new int[digits.length + 1];
        ints[0] = 1;
        return ints;
    }

    /**
     * 2037. 使每位学生都有座位的最少移动次数
     *
     * @param seats
     * @param students
     * @return
     */
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int count = 0;
        for (int i = students.length - 1; i >= 0; i--) {
            count += Math.abs(students[i] - seats[i]);
        }
        return count;
    }

    /**
     * 229. 求众数 II
     *
     * @param nums
     * @return
     */
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int n = nums.length / 3;
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > n) {
                list.add(entry.getKey());
            }
        }
        return list;
    }

    /**
     * 496. 下一个更大元素 I
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums2[i] >= stack.peek()) {
                stack.pop();
            }
            map.put(nums2[i], stack.isEmpty() ? -1 : stack.peek());
            stack.push(nums2[i]);
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }

    /**
     * 367. 有效的完全平方数
     *
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        int index = 1;
        int tempNum = 0;
        while (num > tempNum) {
            tempNum = index * index;
            index++;
        }
        return tempNum == num;
    }

    /**
     * 1518. 换酒问题
     *
     * @param numBottles
     * @param numExchange
     * @return
     */
    public int numWaterBottles(int numBottles, int numExchange) {
        int result = 0;
        do {
            int i = numBottles / numExchange;
            result += numBottles + i;
            numBottles = i + numBottles % numExchange;
        } while (numBottles >= numBottles);
        return result;
    }

    public int dayOfYear(String date) {
        String[] split = date.split("-");
        int year = Integer.valueOf(split[0]);
        int month = Integer.valueOf(split[1]);
        int day = Integer.valueOf(split[2]);
        int dayOfYear = day;
        boolean isRun = (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
        for (int i = 1; i < month; i++) {
            if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 11) {
                dayOfYear += 31;
                continue;
            }
            if (i == 2) {
                dayOfYear += isRun ? 29 : 28;
                continue;
            }
            dayOfYear += 30;
        }
        return dayOfYear;
    }

    /**
     * 适龄的朋友
     *
     * @param ages
     * @return
     */
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int left = 0, right = 0, ans = 0, n = ages.length;
        for (int age : ages) {
            if (age < 15) {
                continue;
            }
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }
            ans += right - left;
        }
        return ans;
    }

    /**
     * 适龄的朋友
     *
     * @param ages
     * @return
     */
    public int numFriendRequests2(int[] ages) {
        int[] cnt = new int[121];
        for (int age : ages) {
            cnt[age]++;
        }
        int[] pre = new int[121];
        for (int i = 1; i <= 120; i++) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int ans = 0;
        for (int i = 15; i <= 120; i++) {
            if (cnt[i] > 0) {
                int bound = (int) (i * 0.5 + 8);
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }

    /**
     * 5963. 反转两次的数字
     *
     * @param num
     * @return
     */
    public boolean isSameAfterReversals(int num) {
        StringBuilder sb = new StringBuilder();
        sb.append(num);
        int num1 = Integer.valueOf(sb.reverse().toString());

        sb = new StringBuilder();
        sb.append(num1);
        int resultNum = Integer.valueOf(sb.reverse().toString());
        return resultNum == num;
    }

    /**
     * 5963. 反转两次的数字
     *
     * @param num
     * @return
     */
    public boolean isSameAfterReversals2(int num) {
        if (num < 10) {
            return true;
        }
        if (num % 10 == 0) return false;
        return true;
    }

    /**
     * 482. 密钥格式化
     *
     * @param s
     * @param k
     * @return
     */
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '-') {
                continue;
            }
            if (count == k) {
                count = 0;
                sb.append("-");
                continue;
            }
            count++;
            sb.append(c > 96 ? (char) (c - 32) : c);
        }
        return sb.reverse().toString();
    }

    /**
     * 面试题 01.01. 判定字符是否唯一
     *
     * @param astr
     * @return
     */
    public boolean isUnique(String astr) {
        int[] ints = new int[123];
        for (int i = 0, len = astr.length(); i < len; i++) {
            char c = astr.charAt(i);
            if (ints[c] > 0) {
                return false;
            }
            ints[c]++;
        }
        return true;
    }

    /**
     * 面试题 01.02. 判定是否互为字符重排
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean CheckPermutation(String s1, String s2) {
        int length = s1.length();
        if (length != s2.length()) return false;
        if (length == 0) return true;
        int[] ints = new int[123];
        for (int i = 0; i < length; i++) {
            ints[s1.charAt(i)]++;
            ints[s2.charAt(i)]--;
        }
        for (int anInt : ints) {
            if (anInt != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 面试题 01.03. URL化
     *
     * @param S
     * @param length
     * @return
     */
    public String replaceSpaces(String S, int length) {
        StringBuilder sb = new StringBuilder(length);
        for (int i = 0; i <= length; i++) {
            if (S.charAt(i) == ' ') {
                sb.append("20%");
                continue;
            }
            sb.append(S.charAt(i));
        }
        return sb.toString();
    }

    /**
     * 面试题 01.06. 字符串压缩
     *
     * @param S
     * @return
     */
    public String compressString(String S) {
        int len = S.length();
        if (len == 0) return S;
        StringBuilder sb = new StringBuilder();
        char pre = S.charAt(0);
        int count = 1;
        for (int i = 1; i < len; i++) {
            char cur = S.charAt(i);
            if (pre != cur) {
                sb.append(pre).append(count);
                pre = cur;
                count = 1;
                continue;
            }
            count++;
        }
        String compressStr = sb.append(pre).append(count).toString();
        return compressStr.length() >= len ? S : compressStr;
    }

    /**
     * 面试题 01.09. 字符串轮转
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s2 + s2).contains(s1);
    }

    /**
     * 面试题 02.01. 移除重复节点 [1, 2, 3, 3, 2, 1, 4]
     *
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode tempNode = new ListNode(-1);
        ListNode curNode = tempNode;
        tempNode.next = head;
        while (head != null) {
            //之前没有重复的
            if (set.add(head.val)) {
                curNode.next = head;
                curNode = head;
            }
            head = head.next;
        }
        curNode.next = null;
        return tempNode.next;
    }

    /**
     * 面试题 02.06. 回文链表 1 2 1 2
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        List<Integer> list = new ArrayList<>();
        ListNode tempNode = null;
        while (head != null) {
            list.add(head.val);
            ListNode temp = head.next;
            head.next = tempNode;
            tempNode = head;
            head = temp;
        }
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            if (iterator.next() != tempNode.val) {
                return false;
            }
            tempNode = tempNode.next;
        }
        return true;
    }

    /**
     * 面试题 02.07. 链表相交
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        //先翻转链表
        ListNode tempHeadA = null;
        while (headA != null) {
            ListNode tempA = headA.next;
            headA.next = tempHeadA;
            tempHeadA = headA;
            headA = tempA;
        }
        ListNode tempHeadB = null;
        while (headB != null) {
            ListNode tempB = headB.next;
            headB.next = tempHeadB;
            tempHeadB = headB;
            headB = tempB;
        }
        boolean flag = true;
        while (tempHeadA != null && tempHeadB != null) {
            if (tempHeadA.val != tempHeadB.val) {
                return flag ? null : tempHeadA;
            }
            flag = false;
            tempHeadA = tempHeadA.next;
            tempHeadB = tempHeadB.next;
        }
        return null;
    }

    /**
     * 2133. 检查是否每一行每一列都包含全部整数
     *
     * @param matrix
     * @return
     */
    public boolean checkValid(int[][] matrix) {
        int n = matrix.length;
        Set<Integer> setRow = new HashSet<>(n);
        Set<Integer> setCol = new HashSet<>(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!setRow.add(matrix[i][j]) || !setCol.add(matrix[j][i])) {
                    return false;
                }
            }
            setRow.clear();
            setCol.clear();
        }
        return true;
    }

    /**
     * 2006. 差的绝对值为 K 的数对数目
     *
     * @param nums
     * @param k
     * @return
     */
    public int countKDifference(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 2006. 差的绝对值为 K 的数对数目
     *
     * @param nums
     * @param k
     * @return
     */
    public int countKDifference2(int[] nums, int k) {
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            count += map.getOrDefault(num - k, 0) + map.getOrDefault(num + k, 0);
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        return count;
    }

    /**
     * 334. 递增的三元子序列
     *
     * @param nums
     * @return
     */
    public boolean increasingTriplet(int[] nums) {
        int length = nums.length;
        if (length < 3) return false;

        return false;
    }

    /**
     * 1447. 最简分数
     *
     * @param n
     * @return
     */
    public List<String> simplifiedFractions(int n) {
        List<String> list = new ArrayList<>();
        Set<BigDecimal> set = new HashSet<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                BigDecimal divide = new BigDecimal(j).divide(new BigDecimal(i), 5, BigDecimal.ROUND_HALF_UP);
                System.out.println(divide);
                if (set.contains(divide)) {
                    continue;
                }
                set.add(divide);
                list.add(j + "/" + i);
            }
        }
        return list;
    }

    /**
     * 1984. 学生分数的最小差值
     *
     * @param nums
     * @param k
     * @return
     */
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans;
    }


    public static void main(String[] args) {

        TestEnum a = TestEnum.B;
        if (a.B == a) {
            TestEnum b = TestEnum.B;
        }

        List<Student> list = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            list.add(new Student(Long.valueOf(i), "第一组" + i));
        }
        for (int i = 0; i < 10000; i++) {
            list.add(new Student(Long.valueOf(i), "第二组" + i));
        }
        for (int i = 0; i < 10000; i++) {
            list.add(new Student(Long.valueOf(i), "第三组" + i));
        }
        long startTime = System.currentTimeMillis();
        List<Student> list1 = list.stream().filter(s -> s.getName().contains("一")).collect(Collectors.toList());
        List<Student> list2 = list.stream().filter(s -> s.getName().contains("二")).collect(Collectors.toList());
        List<Student> list3 = list.stream().filter(s -> s.getName().contains("三")).collect(Collectors.toList());
        long endTime = System.currentTimeMillis();
        System.out.println(list1.size() + " " + list2.size() + " " + list3.size() + " " + (endTime - startTime));
        startTime = System.currentTimeMillis();
        list1 = new ArrayList<>();
        list2 = new ArrayList<>();
        list3 = new ArrayList<>();
        for (Student student : list) {
            if (student.getName().contains("一")) list1.add(student);
            if (student.getName().contains("二")) list2.add(student);
            if (student.getName().contains("三")) list3.add(student);
        }
        endTime = System.currentTimeMillis();
        System.out.println(list1.size() + " " + list2.size() + " " + list3.size() + " " + (endTime - startTime));
//        Map<Long, Student> bizRecordMap = new HashMap<>();
//        Student student = new Student();
//        Student student1 = Optional.ofNullable(bizRecordMap.get(student.getId()))
//                .orElseGet(() -> new Student());
//        System.out.println(student1);
//
//        String url = "https://focusmedia-qualify-dev.oss-cn-shanghai.aliyuncs.com/qualify-upload-module/9193cce21fca4025993f76462161baf8/5dce8b6719d141e683cfa280bf5b31ca?Expires=1640165310&OSSAccessKeyId=LTAIQpJiQh6AHxCp&Signature=nFO3aEi3RN%2BUTf05FGmUXAa6%2BqQ%3D&x-oss-process=image%2Fwatermark%2Ctype_d3F5LXplbmhlaQ%2Ctext_Rk9DVVNNRURJQQ%2Ccolor_FFFFFF%2Ct_20%2Crotate_315%2Cfill_1%2Csize_60";
//        String[] split = url.split("\\?");
//        System.out.println(split[0].substring(split[0].lastIndexOf('/') + 1));
//        Map<String, BigDecimal> storeIdAndAmountMap = new HashMap<>();
//        for (int i = 0; i < 10; i++) {
//            storeIdAndAmountMap.put("1", storeIdAndAmountMap.getOrDefault(
//                    "1", BigDecimal.ZERO).add(new BigDecimal(i)));
//        }
//        System.out.println(storeIdAndAmountMap);
//
//        System.out.println(StoreMealType.valueOf("S_998"));
//        System.out.println(StoreMealType.valueOf("S_1998"));
        System.out.println("==============================");
        Runnable runnable = () -> System.out.println("media");
        Thread thread = new Thread(runnable);
        thread.start();
        System.out.println("focus");


        System.out.println("220208047883".hashCode() % 10);
        String orderId = "220208047883";
        System.out.println(orderId.substring(orderId.length() - 1));
    }
}

enum TestEnum {

    A,
    B,
    C;

}

@Data
@AllArgsConstructor
class Student {
    Long id;
    String name;
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node(int val) {
        this.val = val;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

@Getter
@RequiredArgsConstructor
enum StoreMealType {

    S_998("暂定", BigDecimal.valueOf(998), BigDecimal.valueOf(998), 10, 365, 1, 1),

    S_2998("暂定", BigDecimal.valueOf(2998), BigDecimal.valueOf(2998), 30, 365, 1, 1),

    S_5998("暂定", BigDecimal.valueOf(5998), BigDecimal.valueOf(5998), 60, 365, 1, 1),

    S_8998("暂定", BigDecimal.valueOf(8998), BigDecimal.valueOf(8998), 90, 365, 1, 1);

    /**
     * 名称
     */
    final String name;

    /**
     * 折后价
     */
    final BigDecimal price;

    //final BigDecimal name;

    /**
     * 目录价
     */
    final BigDecimal catalogPrice;

    /**
     * 点位数
     */
    final int locationNum;

    /**
     * 投放天数
     */
    final int day;

    final int highHourNum;

    final int lowHourNum;

//    public static StoreMealDto get(String storeMealId) {
//        var storeMeal = StoreMealType.valueOf(storeMealId);
//        var storeMealDto = new StoreMealDto();
//        if (storeMeal != null) {
//            BeanUtils.copyProperties(storeMeal, storeMealDto);
//            storeMealDto.setStoreMealId(storeMeal.name());
//        }
//        return storeMealDto;
//    }

    public static StoreMealType getByPrice(BigDecimal price) {
        for (StoreMealType value : StoreMealType.values()) {
            if (value.getPrice().doubleValue() == price.doubleValue()) {
                return value;
            }
        }
        return null;
    }

}

class SummaryRanges {

    private List<Integer> list;
    private List<int[]> lists;

    public SummaryRanges() {
        list = new ArrayList<>();
    }

    public void addNum(int val) {
        if (list.contains(val)) return;
        list.add(val);
        Collections.sort(list);
        int first = 0;
        int len = list.size();
        lists = new ArrayList<>();
        for (int i = 1; i < len; i++) {
            if (list.get(i) - list.get(i - 1) == 1) {
                continue;
            }
            lists.add(new int[]{list.get(first), list.get(i - 1)});
            first = i;
        }
        lists.add(new int[]{list.get(first), list.get(len - 1)});
    }

    public int[][] getIntervals() {
        int[][] arr = new int[lists.size()][2];
        for (int i = 0, len = lists.size(); i < len; i++) {
            arr[i] = lists.get(i);
        }
        return arr;
    }
}

class Bank {

    private long[] accounts;

    public Bank(long[] balance) {
        accounts = balance;
    }

    public boolean transfer(int account1, int account2, long money) {
        if (account1 > accounts.length || account2 > accounts.length || accounts[account1 - 1] < money) {
            return false;
        }
        accounts[account1 - 1] -= money;
        accounts[account2 - 1] += money;
        return true;
    }

    public boolean deposit(int account, long money) {
        if (account > accounts.length) {
            return false;
        }
        accounts[account - 1] += money;
        return true;
    }

    public boolean withdraw(int account, long money) {
        if (account > accounts.length || accounts[account - 1] < money) {
            return false;
        }
        accounts[account - 1] -= money;
        return true;
    }
}